/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {

        ListNode* cur = head;

        while (cur && cur->next)
        {
            ListNode* prev = cur->next;
            while (prev && prev->val == cur->val)
            {
                prev = prev->next;
            }

            cur->next = prev;
            cur = cur->next;
        }
        return head;








    }
}; class Solution {
public:
    int kthFactor(int n, int k) {
        int count = 0;
        for (int i = 1; i <= n; i++)
        {
            if (n % i == 0)
            {
                count++;
            }
            if (count == k)
                return i;






        }
        return -1;
    }
};/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* deleteMiddle(ListNode* head) {
        if (head->next == nullptr)
            return nullptr;
        ListNode* cur = head;
        int count = 0;
        while (cur)
        {
            cur = cur->next;
            count++;
        }
        count /= 2;

        ListNode* prev = nullptr;
        cur = head;
        while (count--)
        {
            prev = cur;
            cur = cur->next;
        }
        prev->next = cur->next;
        return head;
    }
}; class Solution {
public:
    int tribonacci(int n) {


        if (n == 0)return 0;
        if (n == 1)return 1;
        if (n == 2)return 1;
        vector<int>dp(n + 1, 0);
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 1;
        for (int i = 3; i <= n; i++)
        {
            dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
        }
        return dp[n];












    }
}; class Solution {
public:
    int tribonacci(int n) {


        if (n == 0)return 0;
        if (n == 1)return 1;
        if (n == 2)return 1;
        vector<int>dp(n + 1, 0);
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 1;
        for (int i = 3; i <= n; i++)
        {
            dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
        }
        return dp[n];












    }
}; class Solution {
public:
    string mergeAlternately(string word1, string word2) {
        int left1 = 0;
        int left2 = 0;
        int end1 = word1.size() - 1;
        int end2 = word2.size() - 1;
        int flag = 1;
        string str;
        int i = 0;
        while (left1 <= end1 && left2 <= end2)
        {
            if (flag == 1)
                str += word1[left1++];
            else
                str += word2[left2++];
            flag *= -1;


        }
        while (left1 <= end1)
        {
            str += word1[left1++];




        }

        while (left2 <= end2)
        {
            str += word2[left2++];




        }
        return str;



    }
}; class Solution {
public:
    vector<int> countBits(int n) {
        vector<int>dp(n + 1);
        for (int i = 0; i <= n; i++)
        {


            int num = i;
            int count = 0;
            while (num)
            {
                if (num & 1)count++;
                num = num >> 1;
            }


            dp[i] = count;





        }

        return dp;







    }
}; class Solution {
public:
    string removeStars(string s) {
        stack<char>st;
        for (auto e : s)
        {
            if (e != '*')
                st.push(e);
            else
            {
                st.pop();

            }





        }
        string str;
        while (st.size())
        {
            str += st.top();
            st.pop();



        }
        reverse(str.begin(), str.end());
        return str;
    }
};/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int maxLevelSum(TreeNode* root) {
        vector<int>res;
        // res[0]=-0x3f3f3f3f;
        res.push_back(INT_MIN);
        queue<TreeNode*>st;
        if (root != nullptr)
            st.push(root);
        while (!st.empty())

        {
            int sum = 0;
            int size = st.size();
            for (int i = 0; i < size; i++)
            {
                TreeNode* find = st.front();
                sum += find->val;
                st.pop();
                if (find->left)
                    st.push(find->left);
                if (find->right)
                    st.push(find->right);
            }
            res.push_back(sum);
            // cout<<sum<<endl;
        }
        int maxi = 0;
        int maxp = INT_MIN;
        for (int i = 0; i < res.size(); i++)
        {
            if (res[i] > maxp)
            {
                maxp = res[i]; maxi = i;
            }





        }
        return maxi;



    }
}; class Solution {
public:
    int strStr(string haystack, string needle) {
        int left1 = 0;
        int left2 = 0;
        int end1 = haystack.size() - 1;
        int end2 = needle.size() - 1;
        int cur = left1;
        while (cur <= end1)
        {
            left1 = cur;
            left2 = 0;
            while (left1 <= end1 && left2 <= end2 && haystack[left1] == needle[left2])
            {
                left1++;
                left2++;
            }

            if (left2 == end2 + 1)
            {
                return cur;
            }
            cur++;
        }

        return -1;

    }
};/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        vector<vector<int>>ans;
        if (root == nullptr)
            return ans;
        queue<TreeNode* >st;
        if (root != nullptr)
            st.push(root);
        while (!st.empty())
        {
            int size = st.size();
            vector<int>path;
            while (size--)

            {
                TreeNode* find = st.front();
                st.pop();
                path.push_back(find->val);
                if (find->left)
                {
                    st.push(find->left);
                }
                if (find->right)
                {
                    st.push(find->right);
                }

            }
            ans.push_back(path);












        }

        reverse(ans.begin(), ans.end());
        return ans;





    }
}; class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int m = nums.size();
        for (int i = 0; i < m; i++)
        {
            while (nums[i] >= 1 && nums[i] <= m && nums[i] != nums[nums[i] - 1])
                swap(nums[i], nums[nums[i] - 1]);
        }
        for (int i = 0; i < m; i++)
        {
            if (nums[i] != i + 1)return i + 1;






        }

        return m + 1;


    }
}; class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        int n = triangle.size();
        vector<vector<int>>dp(n + 1, vector<int>(n + 1));
        for (int i = n - 1; i >= 0; i--)
        {
            for (int j = 0; j <= i; j++)
            {

                dp[i][j] = min(dp[i + 1][j], dp[i + 1][j + 1]) + triangle[i][j];

            }
        }


        return dp[0][0];






    }
};